package com.hackerank.arrays;

/**
 * 二维数组沙漏   2D Array - DS hourglass
 *  https://www.hackerrank.com/challenges/2d-array/problem
 * 题目大意：
 * 1、输入6x6的二维数组，如：
 * 1 1 1 0 0 0
 * 0 1 0 0 0 0
 * 1 1 1 0 0 0
 * 0 0 0 0 0 0
 * 0 0 0 0 0 0
 * 0 0 0 0 0 0
 * 2、定义沙漏形状为：
 * a b c
 *   d
 * e f g
 * 3、则在这个二维数组中存在16个沙漏形状（从第一个元素开始向后遍历，和后两行部分元素组成沙漏形状）
 * 4、计算这16个沙漏形状对应位置的数字之和，如：
 * -9 -9 -9  1 1 1
 *  0 -9  0  4 3 2
 * -9 -9 -9  1 2 3
 *  0  0  8  6 6 0
 *  0  0  0 -2 0 0
 *  0  0  1  2 4 0
 *
 *  16个沙漏的和值按顺序排列如下：
 *  -63, -34, -9, 12,
 * -10, 0, 28, 23,
 * -27, -11, -2, 10,
 * 9, 17, 25, 18
 *
 * 4、输出16个沙漏值里面最大的值，如上 最大值为第7个沙漏的和值28，这个沙漏的和值由
 * 0 4 3
 *   1
 * 8 6 6
 * 计算获得
 *
 * 解题思路：
 * 1、直接遍历二维数组，将对应的沙漏位置[i][j]值求和，并判断是否为最大值
 *
 * 时间复杂度O(c)
 * */
public class Arrays_2D_HourGlassSum {
    static int hourglassSum(int[][] arr) {
        int length = arr.length;
        int sum = 0,max=Integer.MIN_VALUE;
        for(int i=0;i<length-2;i++) {
            for (int j = 0; j < length - 2; j++) {
                sum = arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2];
                if(max < sum){
                    max = sum;
                }
            }
        }
        return max;
    }
}
